#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];

//优化一：随机选择基准元素
int get_random(int left, int right)
{
	return a[rand() % (right - left + 1) + left];
}

void quick_sort(int left, int right)
{
	if(left >= right) return;

	 //1.选择一个基准元素
	int p = get_random(left, right);

	//2.数组分三块 - 荷兰国旗问题
	//小于基准元素 等于基准元素 大于基准元素
	int l = left - 1, i = left, r = right + 1;
	while(i < r)
	{
		if(a[i] < p) swap(a[++l], a[i++]);
		else if(a[i] == p) i++;
		else swap(a[--r], a[i]);
	}

	//[left, l] [l + 1, r - 1] [r, right]
	quick_sort(left, l);
	quick_sort(r, right);
}

int main()
{
	srand(time(0));
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];	
	
	quick_sort(1, n);
	
	for(int i = 1; i <= n; i++) cout << a[i] << " ";	
	
	return 0;
}


// //随机函数的使用
// #include <iostream>
// #include <ctime>

// using namespace std;

// void test()
// {
// 	srand(time(0)); // 种下一个随机数种子

// 	int r1 = rand();
// 	int r2 = rand();
// 	int r3 = rand();

// 	cout << r1 << endl;
// 	cout << r2 << endl;
// 	cout << r3 << endl;

// 	int r4 = rand();
// 	cout << "r4 = " << r4 << endl;
// }

// int main()
// {
// 	test();

// 	return 0;
// }
